package 代码随想录_动态规划.打家劫舍;

/**
 * @author zx
 * @create 2022-06-01 15:46
 */
public class 打家劫舍II_213 {
    /**
     * @return 具体思路参考代码随想录
     */
    public int rob(int[] nums) {
        //情况二：考虑包含首元素，不包含尾元素
        //情况三：考虑包含尾元素，不包含首元素
        if(nums.length == 1){
            return nums[0];
        }
        return Math.max(robRange(nums,0,nums.length - 2),robRange(nums,1,nums.length - 1));
    }
    //198.打家劫舍的逻辑
    private int robRange(int[] nums,int start,int end){
        if(start == end){
            return nums[start];
        }
        int[] dp = new int[nums.length];
        dp[start] = nums[start];
        dp[start + 1] = Math.max(nums[start],nums[start + 1]);
        for(int i = start + 2;i <= end;i++){
            dp[i] = Math.max(dp[i - 2] + nums[i],dp[i - 1]);
        }
        return dp[end];
    }
}
